1. Field of the Invention
The present invention generally relates to a method of generating a symmetrical reversible variable length code.
2. Description of the Prior Art
Variable length codes (hereinafter called VLCs) can achieve higher compression efficiency by assigning codewords with variable code lengths to digital data with non-uniform probability distributions. There are many modern image and video coding standards, such as the JPEG still image coding standard, the ITU series of H.261 and H.263 video coding standards and the ISO series of MPEG-1 and MPEG-2 standards, adopting VLCs as the entropy coding stage. Due to the variable code length nature of VLCs, such schemes are very sensitive to errors in noisy environments. Even one single bit mismatch will cause a serious synchronous problem due to the propagation of errors. Moreover, there are more and more image and video applications being applied and developed in unreliable wireless environments at present time, and the trend will become more important and popular in the future. Therefore, suitable retransmission protocols for less time-constrained applications and adequate VLC code designs for critical time-constrained applications are the main issues for the applications operated in error-prone environments.
A new reversible variable length code (hereinafter called RVLC) has been proposed for the applications operated in the error-prone environments. RVLCs can be decoded both in the forward and backward directions. For example, when an error occurs in the normal forward decoding of a bit stream, the RVLC decoder then proceeds to the end of the bit stream and decodes it in the backward direction. In other words, bit synchronization will not be affected by the propagation of a single bit error. A lot of research topics, such as H.263+and MPEG-4, pay extensive attention on RVLC. Y. Takishima, M. Wada and H. Murakami have proposed a symmetrical RVLC algorithm in the paper, "Reversible Variable Length Code" IEEE Trans. Comm., Vol.43, No.2/3/4, pp.158-163, 1995. The symmetrical RVLC algorithm proposed by Takishima et al. is described in detail as follows.
In this algorithm, the symmetrical RVLC is derived from a Huffman code. The Huffman code, in which digital data are assigned to codewords with optimal bit-lengths according to the known probability distribution of various symbols, is a non-reversible VLC. A RVLC must satisfy both the prefix condition and the suffix condition for instantaneous forward and backward decoding, respectively. If the RVLC satisfies the prefix (or suffix) condition, it means that each codeword does not coincide with the prefixes (or suffixes) of longer codewords. For example, the codeword "1001", which is the prefix of the codeword "100111 (4 bits), does not satisfy the prefix condition. Before discussing this algorithm, some mathematical functions and the codeword properties are described first.
FIG. 1 (Prior Art) is a diagram of a binary tree for illustrating symmetrical codes and non-symmetrical codes. The binary tree begins at root R. Nodes of the next level in the binary tree are obtained by appending a bit of "0" or "1," where appending "0" and "1" can generate a new code on the left side and on the right side, respectively. In FIG. 1, there are five levels, denoted by L1.about.L5, in this binary tree. The nodes on these levels correspond to codes with the code lengths from 1 to 5, respectively. For a symmetrical code, such as 11011 (node 5g), the bit sequences read from left to right and from right to left are the same. On the contrary, the non-symmetrical codeword, such as 10011, does not possess such bit sequence property. In FIG. 1, the nodes corresponding to symmetrical codes are represented by full circles and the nodes corresponding to non-symmetrical codes are represented by empty circles. If all codewords of a VLC are symmetrical, the VLC is reversible. Reversibility means that digital data can be decoded in the forward direction or in the backward direction. The number of the codes that have length L and can be instantaneously decoded, denoted by m(L), is determined as follows.
On a full binary tree as illustrated in FIG. 1, the number of symmetrical codes with length L, denoted by m.sub.0 (L), is calculated as follows: EQU m.sub.0 (L)=2.sup..left brkt-bot.(L+1)/2.right brkt-bot. (1)
where .left brkt-bot.x.right brkt-bot. denotes the ceiling function, which is the smallest integer or equal to x. The relation between L and m.sub.0 (L) determined by equation (1) is illustrated in Table 1. PA1 (a) u(i,L)=m.sub.0 (L-2i), when i.ltoreq.L/2; PA1 (b) u(i,L)=1 or 0, when L/2&lt;i&lt;L; PA1 (c) u(i,L)=0, in all other cases. PA1 where n(i) denotes the number of codewords with length i in the original VLC and x(i,L) denotes the number of codewords with length i whose (2i-L) suffixes are symmetrical. In equation (2), the second term and the third terms are used to calculate the total number of symmetrical codes due to the violation of the prefix condition in case (a) and case (b), respectively. Therefore, the symmetrical codes with length L which satisfy the instantaneous decoding condition, denoted by m(L), can be acquired by deleting the codewords that violate the prefix condition from the symmetrical codewords with length L, denoted by m.sub.0 (L).
L 1 2 3 4 5 6 7 8 m.sub.0 (L) 2 2 4 4 8 8 16 16
Not all of the symmetrical codes decided by equation (1) satisfy the instantaneous decoding condition. The symmetrical codes that satisfy the prefix condition and the suffix condition belong to those defined in m(L). Refer to the binary tree shown in FIG. 1 and consider a path from the root R to a leaf node at level L, such as the path 1a -2a -3a -4a -5a. In such a path, the codes corresponding to the nodes in the head are the prefix of the codes corresponding to the nodes in the tail. In other words, only one node can be selected as a candidate in a path. Selecting two or more nodes in a path can result in the violation of the prefix condition. Therefore, m(L) can be derived from m.sub.0 (L) by deleting the nodes that could violate the prefix condition. Let u(i,L) denotes the number of symmetrical codes with length L that violate the prefix condition when a node at the i-th level is selected as a candidate. There are three different cases.
According to conditions (a), (b) and (c), the number of symmetrical codes with length L that can be assigned to an instantaneously decodable VLC, denoted by m(L), is given as follows: ##EQU1##
The symmetrical RVLC algorithm proposed by Takishima et al. derives a RVLC from an original VLC, such as the Huffman code, by using the function m(L).
Step 1:
The bit length vector n.sub.rev (i) of the target RVLC is initialized to be the bit length vector n(i) of the original VLC (such as the Huffman code). The component of a bit length vector indicates the number of the codewords with length i. Accordingly, n.sub.rev (i)=n(i).
Step 2:
For every i, the condition n.sub.rev (i).ltoreq.m(i) is examined, where n.sub.rev (i) denotes the number of the codewords with length i and m(i) denotes the number of the symmetrical codes with length i which satisfy the instantaneous decoding condition. Accordingly, when n.sub.rev (i).ltoreq.m(i), it means that the number of the symmetrical codes is enough to be assigned to the codewords with length i in the target RVLC. When the condition is not satisfied, it means that the assignment requires the codes with length i+1. At this time, the bit length vector n.sub.rev (i) of the target RVLC must be adjusted: EQU n.sub.rev (i+1)=n.sub.rev (i+1)+n.sub.rev (i)-m(i (3) EQU n.sub.rev (i)=m(i (4)
In equation (4), n.sub.rev (i) is set to be the maximal possible number, m(i). The other unassigned codewords with length i (that is, n.sub.rev (i)-m(i)) are assigned by the codes with length i+1. It is noted that m(i) does not only depend on the bit length vector n.sub.rev (i), but also on the bit alignment pattern of each codeword in the original VLC.
Step 3:
Step 2 is repeated until every codeword has been assigned.
In the conventional Takishima's algorithm, there are three terms in equation (2) for determining m(L). The first and second terms are determined only by the code length L and the bit length vector n(i), while the last term depends on the bit alignment pattern of each codeword. This indicates the fact that a symmetrical RVLC with a different bit length vector can be generated from VLCs with an identical bit length vector but different bit alignment patterns. In practice, the bit length vector can make extensive influence on coding efficiency. It is evident that using codewords with shorter bit lengths may make the average length shorter. Accordingly, the first drawback of the conventional algorithm is that the coding efficiency, which depends on the bit alignment patterns of codewords in the original VLC, is hard to control. In addition, since the bit alignment patterns of the codewords should be considered, the prefix or suffix condition is easily violated during the assigning of the symmetrical codewords. This is the second drawback of the conventional Takishima's algorithm.